#ifndef TIM_LIST_H
#define TIM_LIST_H
#include<bits/stdc++.h>

namespace tim
{
	template<typename T>
	class node
	{
		public:
			T  data;//数据域
			node<T>* pred;//前驱
			node<T>* succ;//后继
			//node() {};//对header 和 trailer的构造
			node(): pred(NULL), succ(NULL) {};
			node(T const& e, node<T>* p = NULL, node<T>* s = NULL): data(e), pred(p), succ(s) {}; //默认构造
			void insert_pred(node<T>* p);//插入前驱
			void insert_succ(node<T>* s);//插入后继
	};

	template<typename T>
	class list
	{
		protected:
			void init();//创建头尾哨兵
			node<T>* header;//头哨兵
			node<T>* trailer;//尾哨兵
			int _size;//当前规模建头尾哨兵
			node<T>* first() { return header->succ; };//获得首结点
			node<T>* last() { return trailer->pred; };//获得尾结点
			node<T>* get(int n);//获得任意结点，复杂度o（n）
			bool insert_sort(bool order);//选择排序
			bool merge_sort(bool order, int hi, int lo, node<T>* last);//归并排序

		public:
			list() { init();};
			list(tim::list<T> const& old_one);//从旧链表生成，时间复杂度o（n）
			list(tim::list<T>& old_one, int begin, int end);//可选开始与结束
			list(int s, T e = T());//诞生空链表， 指定零元，时间复杂度o（n）
			list(T* begin, T* end);//从数组诞生，时间复杂度o（n）
			~list();//释放空间，o（n）
			bool is_empty() { return _size == 0;};//判空
			bool insert(int n, T const& e);//任意插入，复杂度o（n）
			bool insert_front(T const& e);//头插法，复杂度o（1）
			bool insert_back(T const& e);//尾插法
			bool remove(int begin, int end);//区间删除，复杂度o（n）, 左闭右开
			T remove(int n); //特化
			T remove_front();//头删法, 复杂度o（1）
			T remove_back();//尾删法，复杂度o（1）
			bool inverse();//链表反转，复杂度o（n）
			int find(T const& e);//查找，返回秩, o（n)复杂度
			int bin_find(T const& e, bool is_sort, int lo = 0, int hi = 0); //二分查找，返回秩, o(logn)复杂度
			bool sort(bool mode = true, bool order = true);//排序，mode true时使用插入排序, 否则使用归并排序，order决定正逆序
			int size() { return _size; };//返回规模
			T& operator[] (int n);//仿数组接口，时间复杂度o（n）
			template<typename VST>
			void traverse(VST& visit);//遍历, 时间复杂度o（n）
	};
}

template<typename T>
void tim::node<T>::insert_pred(node<T>* p)
{
	pred = p;
}

template<typename T>
void tim::node<T>::insert_succ(node<T>* s)
{
	succ = s;
}
template<typename T>
void tim::list<T>::init()
{
	header = new node<T>;
	trailer = new node<T>;

	header->insert_succ(trailer);
	header->pred = nullptr;
	trailer->insert_pred(header);
	trailer->succ = nullptr;
	_size = 0;
}

template<typename T>
tim::list<T>::list(T* begin, T* end)
{
	init();
	_size = end - begin;

	for (int i = 0; i < _size; i++) {
		node<T>* new_node = new node<T>(begin[i], trailer->pred, trailer);
		trailer->pred->succ = new_node;
		trailer->insert_pred(new_node);
	}
}

template<typename T>
tim::list<T>::list(int n, T e)
{
	init();
	_size = n;

	for (int i = 0; i < n; i++) {
		node<T>* new_node = new node<T>(e, trailer->pred, header);
		trailer->pred->succ = new_node;
		trailer->insert_pred(new_node);
	}
}

template<typename T>
tim::list<T>::list(tim::list<T> const& old_one)
{
	init();
	for (node<T>* temp = old_one.header->succ; temp->succ != nullptr; temp = temp->succ) {
		node<T>* new_node = new node<T>(temp->data, trailer->pred, trailer);
		trailer->pred->succ = new_node;
		trailer->pred = new_node;
	}
	_size = old_one._size;
}

template<typename T>
tim::list<T>::list(tim::list<T>& old_one, int begin, int end)
{
	init();
	int cnt = begin;

	for (node<T>* temp = old_one.first(); temp->next != nullptr; temp = temp->next, cnt++) {
		if (cnt >= begin and cnt < end) {
			node<T>* new_node = new node<T>(temp->data, trailer->pred, trailer);
			trailer->pred->next = new_node;
			trailer->pred = new_node;
		}
	}
}

template<typename T>
T& tim::list<T>::operator[](int n)
{
	node<T>* temp = first();
	for (int i = 0 ; i < n; temp = temp->succ, i++);
	return temp->data;
}

template<typename T>
template<typename VST>
void tim::list<T>::traverse(VST& visit)
{
	for (node<T>* temp = first(); temp->succ != nullptr; temp = temp->succ)
		visit(temp->data);
}

template<typename T>
tim::list<T>::~list()
{
	node<T>* temp1 = header;
	node<T>* temp2 = temp1;

	while (temp2 != nullptr) {
		temp2 = temp1->succ;
		delete temp1;
		temp1 = temp2;
	}

	delete temp1;
}

template<typename T>
bool tim::list<T>::insert(int n, T const& e)
{
	if (n > _size or n < 0 ) return false;

	node<T>* temp = first();
	for (int i = 0; i < n; i++, temp = temp->succ);
	node<T>* new_node = new node<T>(e, temp->pred, temp);
	temp->pred->succ = new_node;
	temp->pred =  new_node;
	_size++;

	return true;
}

template<typename T>
bool tim::list<T>::insert_front(T const& e)
{
	node<T>* new_node = new node<T>(e, header, header->succ);
	header->succ->pred = new_node;
	header->succ = new_node;
	_size++;
	return true;
}

template<typename T>
bool tim::list<T>::insert_back(T const& e)
{
	node<T>* new_node = new node<T>(e, trailer->pred, trailer);
	trailer->pred->succ = new_node;
	trailer->pred = new_node;
	_size++;
	return true;
}

template<typename T>
bool tim::list<T>::remove(int begin, int end)
{
	if (begin < 0 or end > _size or begin > end) return false;

	_size -= end - begin;
	node<T>* be = first();
	node<T>* en = first();
	for (int i = 0; i < begin; i++, be = be->succ);
	for (int i = 0; i < end; i++, en = en->succ);
	node<T>* be2 = be->pred;
	while( be != en) {
		node<T>* temp = be;
		be = be->succ;
		delete temp;
	}
	be2->succ = en;
	en->pred = be2;

	return true;
}

template<typename T>
int tim::list<T>::find(T const& e)
{
	int rank = 0;
	for(node<T>* temp = header->succ; temp->succ != nullptr and e != temp->data; rank++, temp = temp->succ);
	if (rank < this->size()) return rank;
	else return -1;
}

template<typename T>
int tim::list<T>::bin_find(T const& e, bool is_sort, int lo, int hi)
{
	if (!is_sort) this->sort(true, true);
	if (hi == 0) hi = _size;

	if (hi - lo < 2) {
		if (this->operator[](hi) == e) return hi;
		else if (this->operator[](lo) == e) return lo;
		else return 0;
	}
	int mi = (hi + lo) / 2;
	if (e <= this->operator[](mi)) return bin_find(e, true, lo, mi);
	else return bin_find(e, true, mi, hi);
}

template<typename T>
bool tim::list<T>::inverse()
{
	node<T>* temp = first(), *temp2 = last();
	for(; temp != temp2 and temp2->succ != temp; temp = temp->succ, temp2 = temp2->pred) {
		T a;

		a = temp->data;
		temp->data = temp2->data;
		temp2->data = a;
	}

	return true;
}

template<typename T>
bool tim::list<T>::sort(bool mode, bool order)
{
	return mode ? insert_sort(order): merge_sort(order, 0, _size, last());
}

template<typename T>
bool tim::list<T>::insert_sort(bool order)
{
	for (int i = 0; i < _size; i++) {
		int j;

		for (j = 0; j < i; j++)
			if (this->operator[](j) > this->operator[](i)) break;
		insert(j, remove(i));
	}

	return true;
}

template<typename T>
tim::node<T>* tim::list<T>::get(int n)
{
	node<T>* temp = header->succ;
	for (int i = 0; i < n; i++, temp = temp->succ);
	return temp;
}

template<typename T>
T tim::list<T>::remove(int n)
{
	T re = get(n)->data;
	remove(n, n + 1);
	return re;
}

template<typename T>
T tim::list<T>::remove_back()
{
	node<T>* temp = last();
	T re = temp->data;
	temp->pred->succ = trailer;
	trailer->pred = temp->pred;
	delete temp;
	_size--;
	return re;
}

template<typename T>
T tim::list<T>::remove_front()
{
	node<T>* temp = first();
	T re;
	re = temp->data;
	temp->succ->pred = header;
	header->succ = temp->succ;
	delete temp;
	_size--;
	return re;
}

template<typename T>
bool tim::list<T>::merge_sort(bool order, int lo, int hi, node<T>* last)
{
	/*if (hi - lo < 2) return false;

	int mi = (hi + lo) / 2;
	merge_sort(order, lo, mi, get(mi));
	merge_sort(order, mi, hi, last);
	tim::list<T> list_a = tim::list<T>(*this, lo, mi);
	tim::list<T> list_b = tim::list<T>(*this, mi, hi);
	remove(lo, hi);

	for (int i = lo, a = 0, b = 0; i < hi; i++) {
		node<T>* new_node = new node<T>;
		node<T>* temp_a = list_a.first();
		node<T>* temp_b = list_b.first();

		if (temp_a->succ == nullptr) {
			new_node->data = temp_b->data;
			temp_b = temp_b->succ;
		}
		else if (temp_b->succ == nullptr) {
			new_node->data = temp_a->data;
			temp_a = temp_a->succ;
		}
		else {
			if ((temp_a->data < temp_b->data) == order) new_node->data = temp_a->data;
			else new_node->data = temp_a->data;
		}
		last->insert_pred(new_node);
		last->pred->succ = new_node;
		new_node->pred = last->pred;
		new_node->succ = last;
	}*///wait!

	return true;
}

#endif
